A data "structure" refers to related data stored in a computer memory location. To enhance operating efficiency, a data structure may be "shared" by a plurality of processors which require the same information to perform various tasks. Synchronizing access to a shared data structure is a great challenge in designing software for computers with multiple processors, and is especially important whenever multiple processors attempt to update information in a data structure. Indeed, without synchronization, the performance of a system including a shared data structure is severely degraded. This is because when one processor performs a data structure update, it is common for the entire data structure to be inaccessible (or "locked") to other processors. In other words, the non-updating processors must wait until the data structure is "unlocked" before the information contained in the structure can be accessed or updated. Another significant problem affecting the performance of a multiprocessor environment with shared resources is the inability of multiple processors to simultaneously perform updates on discrete data structure events without blocking each other.
Therefore, there is a need for an efficient, non-blocking operation for updating shared data structures while maintaining FIFO behavior in a multiprocessor environment.